package BinaryTree;

public class BinaryTree implements BinarySearchTreeInterface{

    BinaryNode root;

    static class BinaryNode {
        public int key;
        public Object value;
        BinaryNode left;
        BinaryNode right;

        public BinaryNode(int key,Object value) {
            this.key = key;
            this.value = value;

        }

        public BinaryNode (int key,Object value, BinaryNode left, BinaryNode right ) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }

    @Override
    public Object get(int key) {
        if (root == null) {
            return null;

        }
        BinaryNode p = root;
        while (p != null) {
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                return p.value;
            }

        }
        return null;
    }

    @Override
    public Object min() {

        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while (p.left != null) {
            p = p.left;
        }

        return p.value;
    }

    //重载 min 方法
    public Object min(BinaryNode node) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while (p.left != null) {
            p = p.left;
        }

        return p.value;
    }
    //使用递归实现查找最小关键字
    public Object minRecursion(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p =doMin(node);
        return p.value;
    }
    private BinaryNode doMin(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node;
        }
        return doMin(node.left);
    }


    @Override
    public Object max() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while (p.right != null) {
            p = p.right;

        }
        return p.value;
    }
    //重载 max 方法
    public Object max(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.right != null) {
            p = p.right;

        }
        return p.value;
    }
    //使用递归实现
    public Object maxRecursion(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = doMax(node);
        return p.value;
    }
    private BinaryNode doMax(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node;
        }
        return doMax(node.right);

    }

    @Override
    public void put(int key, Object value) {
        if (root == null) {
            root = new BinaryNode(key,value);
            return;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            parent = p;
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                p.value = value;
                return;
            }
        }
        if (parent.key > key) {
            parent.left = new BinaryNode(key,value);
        } else {
            parent.right = new BinaryNode(key, value);
        }

    }

    @Override
    public Object successor(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode parent = null;
        BinaryNode p = root;
        while (p != null) {
            if (p.key > key) {
                parent = p;
                p = p.left;
            }else if (p.key < key) {

                p = p.right;
            }else {
                break;
            }
        }

        //不存在该关键字节点
        if (p == null ) {
            return null;
        }

        if (p.right != null) {
            return min(p.right);
        }
        return parent == null ? null : parent.value;
    }

    @Override
    public Object predecessor(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode parent = null;
        BinaryNode p = root;
        while(p != null) {
            if (p.key > key) {
                p = p.left;
            }else if (p.key < key) {
                parent = p;
                p = p.right;
            }else {
             break;
            }
        }
        if (p == null) {
            //找不到该值
            return null;
        }
        //需要判断是否有左子树
        //情况一:该节点存在左子树
        if (p.left != null) {
            //该前驱就为左子树的最大关键字
            return max(p.left);
        }
        //情况二:该节点不存在左子树，
        //该前驱的节点就为从左向右而来的祖宗
        if (parent == null) {
            return null;
        }
        return parent.value;
    }

    @Override
    public Object delete(int key) {
        if (root == null) {
            return null;
        }
        //先需要找到该删除节点
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            if (p.key > key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            }else {
                break;
            }
        }
        if (p == null) {
            //没有找到需要删除的关键节点，直接返回 null 即可
            return null;
        }
        BinaryNode ret = p;
        //删除有四种情况
        //第一种:该删除的节点只有左子节点
        if ( p.right == null) {
            //需要找到该删除节点的删除节点
            //该删除的节点由于是链接在父母节点的左边,所以该删除节点的孩子节点同样也是链接左边
            swap(parent,p,p.left);
        }else if (p.left == null ) {
            swap(parent,p,p.right);
        }else {
            //该删除的节点存在左右子树
            //需要先找到该删除节点后驱节作为“替补”
            BinaryNode s = p.right;
            BinaryNode sParent = s;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            if (sParent == s) {
                //可以直接顶替删除节点的位置了
                swap(parent,p,s);
                s.left = p.left;
            } else {
                swap(sParent,s,s.right);
                swap(parent,p,s);
                s.left = p.left;
                s.right = p.right;
            }
        }

        return ret.value;
    }
    private void swap(BinaryNode parent, BinaryNode delete, BinaryNode next) {
        if (parent == null) {
            root = next;
        } else if (parent.key > delete.key) {
            parent.left = next;
        }else {
            parent.right = next;
        }
    }
}
